//--------------------------------------------------------------------------------------//
//                                                                                      //
//    __  __  __    __    __  ___   __   ___  __    ___    __  __  __  ___  ___  __     //
//   / _)/  \(  )  (  )  (  )(   \ (  ) (  ,)(  )  (  _)  (  \/  )/  \(   \(  _)(  )    //
//  ( (_( () ))(__  )(__  )(  ) ) )/__\  ) ,\ )(__  ) _)   )    (( () )) ) )) _) )(__   //
//   \__)\__/(____)(____)(__)(___/(_)(_)(___/(____)(___)  (_/\/\_)\__/(___/(___)(____)  //
//                                                                                      //
//                                                                                      //
//       Copyright by Theodor Mader, 2009                                               //
//			www.theomader.com/public/Projects.html                                      //
//--------------------------------------------------------------------------------------//

#include <iostream>
#include <queue>
#include <windows.h>

#include "BspTree.h"
#include "threading.h"

using namespace Geometry;
using namespace Threading;

BspNode::BspNode( const Plane& separatingPlane ) 
{
	this->separatingPlane = separatingPlane;
	pos = 0;
	neg = 0;

}

BspTree::BspTree( const std::vector<Vertex>& vertices, unsigned int numVerticesPerLeaf ) 
	: m_Vertices( vertices )
{
	m_iNumVerticesPerLeaf = numVerticesPerLeaf;
}

BspTree::~BspTree() 
{
	if( m_pRoot ) 
		DeleteTree( m_pRoot );
}

void BspTree::DeleteTree( BspNode*& root ) 
{
	if( root ) 
	{
		DeleteTree( root->pos );
		DeleteTree( root->neg );

		delete root;
		root = 0;
	}
}


void BspTree::BuildMT( unsigned int numThreads )
{
	// create our task scheduler
	Threading::Scheduler scheduler( m_Vertices, m_iNumVerticesPerLeaf, numThreads );

	// create the initial task
	Threading::Task *rootTask = new Threading::Task( m_pRoot );
	rootTask->indices.resize( m_Vertices.size() );
	for( unsigned int i=0; i<m_Vertices.size(); i++ )
		rootTask->indices[i] = i;

	// add task to scheduler and start processing
	scheduler.AddTask( rootTask );
	scheduler.StartProcessing();
}

void BspTree::Build()
{
	Threading::Task *rootTask = new Threading::Task( m_pRoot );
	rootTask->indices.resize( m_Vertices.size() );
	for( unsigned int i=0; i<m_Vertices.size(); i++ )
		rootTask->indices[i] = i;

	// add task to scheduler and start processing
	BuildSubtree( *rootTask );
}


std::list<Task*> BspTree::BuildNode( Task& task, const std::vector<Vertex>& vertices, const unsigned int numVerticesPerLeaf )
{
	// create result list
	std::list<Task*> newTasks;

	// calculate separating plane, create bsp node
	Plane sep = SeparatingPlane( task.indices, vertices );
	task.node = new BspNode( sep );

	// partition vertices into both halfspaces defined by separating plane
	unsigned int numPos = 0;
	unsigned int numNeg = 0;

	Task* pTaskPosSide = new Task( task.node->pos );
	Task* pTaskNegSide = new Task( task.node->neg );
		
	// preallocate memory for faster insertions
	pTaskPosSide->indices.reserve( task.indices.size() / 2 );
	pTaskNegSide->indices.reserve( task.indices.size() / 2);

	for( unsigned int i=0; i<task.indices.size(); i++ ) 
	{
		unsigned int curVertex = task.indices[i];

		float side = vertices[curVertex].x * sep.x + vertices[curVertex].y * sep.y
			+ vertices[curVertex].z * sep.z + sep.d;

		if( side > 0.0f ) {
			numPos++;
			pTaskPosSide->indices.push_back( curVertex );
		}

		else{
			numNeg++;
			pTaskNegSide->indices.push_back( curVertex );
		}
	}

	// schedule task for positive side (if more than numVerticesPerPlane on this side)
	if( numPos > numVerticesPerLeaf )
		newTasks.push_back( pTaskPosSide );
	else {
		task.node->pos = new BspNode();
		delete pTaskPosSide;
	}

	// schedule task for negative side (if more than numVerticesPerPlane on this side)
	if( numNeg > numVerticesPerLeaf )
		newTasks.push_back( pTaskNegSide );
	else {
		task.node->neg = new BspNode();
		delete pTaskNegSide;
	}

	return newTasks;
}

/*!	Takes the list of vertices, partitions them according to maximum variance (\see 
*	separatingPlane() ), and goes on partitioning the left and right half. Recursion is
*	ended when only \a numVerticePerBin vertices are left. 
*
*	\note Recursion was replaced by an iterative algorithm due to speed and memory constraints	*/
void BspTree::BuildSubtree( Threading::Task& task ) 
{
	std::list<Threading::Task*> taskList;
	taskList.push_back( &task );

	// while there are tasks left:
	while( !taskList.empty() ) 
	{
		// pop first task
		Task* curTask = taskList.front();

		// construct current bsp node and add new tasks to toProcess
		std::list<Task*> newTasks = BuildNode( *curTask, m_Vertices, m_iNumVerticesPerLeaf );

		// delete current task
		taskList.pop_front();
		delete curTask;

		// add new tasks to task list
		taskList.insert( taskList.begin(), newTasks.begin(), newTasks.end() );
	}
}


/*!	Opens \a fileName in binary writing mode, writes the number of nodes as unsigned int first
*	and finally calls recWriteToFile()														*/
bool BspTree::SaveToFile( std::string fileName ) 
{
	std::ofstream outFile( fileName.c_str(), std::ios_base::binary );
	if( !outFile.good() )
		return false;

	// write recursively to file
	RecWriteToStream( outFile, *m_pRoot );
	outFile.close();

	return true;

}

bool BspTree::SaveToBuffer( char* destination, unsigned long size )
{
	unsigned long n = ComputeRequiredBufferSize();
	if( size < n ) return false;

	// start writing recursively to buffer
	unsigned long position = 0;
	RecWriteToBuffer( destination, position, *m_pRoot, size ); 

	return true;

}

/*!	Traverses the tree in inorder, writing the separating plane at each node to \a file		*/
void BspTree::RecWriteToStream( std::ostream& stream, const BspNode& node ) 
{
	// write node to file
	node.separatingPlane.WriteToStream( stream );

	// have we reached a leaf?
	if( !node.separatingPlane.Valid() )
		return;

	// recursively write left and right subtree to file
	RecWriteToStream( stream, *node.pos );
	RecWriteToStream( stream, *node.neg );
}

void BspTree::RecWriteToBuffer( char *buffer, unsigned long& position, const BspNode& node, unsigned long size )
{
	position = node.separatingPlane.WriteToBuffer( buffer, position, size );

	// have we reached a leaf?
	if( !node.separatingPlane.Valid() )
		return;

	// recursively write left and right subtree to file
	RecWriteToBuffer( buffer, position, *node.pos, size );
	RecWriteToBuffer( buffer, position, *node.neg, size );
}


/*!	Recursively traverses the tree, counting the nubmber of nodes		*/
unsigned long BspTree::NumNodes( BspNode* node ) 
{
	if( !node->separatingPlane.Valid() )
		return static_cast<long>( 1 );

	return static_cast<long>( 1 ) + NumNodes( node->pos ) + NumNodes( node->neg );
}

/*!	Recursively traverses the tree, counting the nubmber of nodes		*/
unsigned long BspTree::NumLeafs( BspNode* node ) 
{
	if( !node->separatingPlane.Valid() )
		return static_cast<long>( 1 );

	return NumLeafs( node->pos ) + NumLeafs( node->neg );

}

unsigned long BspTree::RequiredBufferSize( BspNode* node ) 
{
	if( !node->separatingPlane.Valid() )
		return node->separatingPlane.RequiredBufferSize();

	return node->separatingPlane.RequiredBufferSize() + RequiredBufferSize( node->pos ) + RequiredBufferSize( node->neg );
}

